import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

import org.junit.Test;

public class MyTest {

    public int networkDelayTime(int[][] times, int n, int k) {
        int infite=Integer.MAX_VALUE/2;
        List<int[]>[] map=new List[n];
        for(int[] time:times){
            if(map[time[0]-1]==null){
                map[time[0]-1]=new ArrayList<int[]>();
            }
            map[time[0]-1].add(new int[]{time[1]-1,time[2]});
        }
        int[] found=new int[n];
        Arrays.fill(found, infite);
        found[k-1]=0;
        Queue<int[]> notFound=new PriorityQueue<int[]>(
            (first,second)->{
                if(first[1]-second[1]==0){
                    return first[0]-second[0];
                }else{
                    return first[1]-second[1];
                }
            }
        );
        notFound.offer(new int[]{k-1,0});
        while(!notFound.isEmpty()){
            int[] curr=notFound.poll();
            if(found[curr[0]]<curr[1]){
                continue;
            }
            if(map[curr[0]]!=null){
                for(int[] next:map[curr[0]]){
                    next[1]+=curr[1];
                    if(found[next[0]]>next[1]){
                        notFound.offer(next);
                        found[next[0]]=next[1];
                    }
                }
            }
        }
        int min=0;
        for(int time:found){
            min=Math.max(min, time);
        }
        return min==infite?-1:min;
    }
    
    public void reverseString(char[] s) {
        int left=0,right=s.length-1;
        char temp;
        while(left<right){
            temp=s[left];
            s[left]=s[right];
            s[right]=temp;
            left++;
            right--;
        }
    }
    
    public String reverseWords(String s) {
        int p=0,left=0,right=0;
        char temp;
        char[] sChar=s.toCharArray();
        while(p<sChar.length){
            while(p<sChar.length&&sChar[p]!=' '){
                p++;
            }
            right=p-1;
            while(left<right){
                temp=sChar[left];
                sChar[left]=sChar[right];
                sChar[right]=temp;
                left++;
                right--;
            }
            p++;
            left=right=p;
        }
        return new String(sChar);
    }

    public boolean exist(char[][] board, String word) {
        boolean[][] isReached=new boolean[board.length][board[0].length];
        for(int x=0;x<board.length;x++){
            for(int y=0;y<board[0].length;y++){
                if(board[x][y]==word.charAt(0)){
                    if(DFS(board, isReached, x, y, new StringBuffer(word))){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private boolean DFS(char[][] board,boolean[][] isReached,int x,int y,StringBuffer word){
        isReached[x][y]=true;
        StringBuffer sBuffer=new StringBuffer(word.toString());
        sBuffer.deleteCharAt(0);
        if(sBuffer.length()==0){
            return true;
        }
        if(x-1>=0&&!isReached[x-1][y]&&board[x-1][y]==sBuffer.charAt(0)){
            boolean flag=DFS(board, isReached, x-1, y, sBuffer);
            if(flag){
                return true;
            }
        }
        if(y-1>=0&&!isReached[x][y-1]&&board[x][y-1]==sBuffer.charAt(0)){
            boolean flag=DFS(board, isReached, x, y-1, sBuffer);
            if(flag){
                return true;
            }
        }
        if(x+1<board.length&&!isReached[x+1][y]&&board[x+1][y]==sBuffer.charAt(0)){
            boolean flag=DFS(board, isReached, x+1, y, sBuffer);
            if(flag){
                return true;
            }
        }
        if(y+1<board[0].length&&!isReached[x][y+1]&&board[x][y+1]==sBuffer.charAt(0)){
            boolean flag=DFS(board, isReached, x, y+1, sBuffer);
            if(flag){
                return true;
            }
        }
        isReached[x][y]=false;
        return false;
    }

    @Test
    public void test(){
        char[][] board={{'C','A','A'},{'A','A','A'},{'B','C','D'}};
        String word="AAB";
        System.out.println(exist(board, word));
    }
}
